#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

using namespace std;

void random_initialization(int popNum, int length, int* codes, int codeNum, int* codeCount, int** iniPop) {
    int i, j;
    int* nJs = new int[codeNum]; // 统计每个编码产生的数量
    random_device rd;
    mt19937 random(rd());
    uniform_int_distribution<int> dist(0, codeNum - 1);
    for (int k = 0; k < popNum; k++) {
        // 给元素赋值1-codeNum的数
        iniPop[k][0] = dist(random) + 1;
        for (i = 1; i < codeNum;) {
            iniPop[k][i] = dist(random) + 1;
            for (j = 0; j < i; j++) {
                // 若有相同元素则重新赋值
                if (iniPop[k][i] == iniPop[k][j])
                    break;
            }
            // 只有i之前的元素全部不相同，才进行i++，对下一个元素赋值
            if (j == i)
                i++;
        }
    }
}

double compute_fitness(int* pop, int length, int** a) {
    // 计算个体适应度
    double fitness = 0.0;
    for (int i = 1; i < length; i++)
        fitness += a[pop[i - 1] - 1][pop[i] - 1];
    fitness += a[pop[length - 1] - 1][pop[0] - 1];

    // 适应度函数
    return 1 / fitness;
}

void copy_gh(int k, int kk, int length, int** iniPop1) {
    // 父代种群
    int** iniPop = iniPop1;
    for (int i = 0; i < length; i++)
        iniPop1[k][i] = iniPop[kk][i];
}

void round_bet(int popNum, int length, int** iniPop1, double* fitness) {
    // 楼盘赌
    random_device rd;
    mt19937 random(rd());
    uniform_real_distribution<double> dist(0, 1);
    for (int k = 0; k < length; k++) {
        double ran1 = dist(random);
        int i;
        for (i = 0; i < length; i++) {
            if (ran1 <= fitness[i])
                break;
        }
        if (i == length)
            i--;
        int selectId = i;
        copy_gh(k, selectId, length, iniPop1);
    }
}

void disturbance(int** iniPop, int popNum, int length, int disPos) {
    // 扰动
    // 交叉概率
    double pCross = 0.8;
    // 变异概率
    double pMutate = 0.9;
    random_device rd;
    mt19937 random(rd());
    uniform_real_distribution<double> dist(0, 1);
    // 交叉
    for (int i = 0; i < popNum; i += 2) {
        if (dist(random) <= pCross) {
            for (int j = 0; j < disPos; j++) {
                int t = iniPop[i][j];
                iniPop[i][j] = iniPop[i + 1][j];
                iniPop[i + 1][j] = t;
            }
            // 对交叉过后的重复数组进行修复
            int re = i - 1;
            while (++re <= i + 1) {
                // 统计每个编码产生的数量
                int* njs = new int[length];
                for (int j = 0; j < length; j++)
                    // 初始是=时均为出现，置为0
                    njs[j] = 0;
                for (int j = 0; j < length; j++) {
                    // 获取位置
                    int pos = iniPop[re][j] - 1;
                    // 统计出现次数
                    njs[pos]++;
                    if (njs[pos] > 1)
                        // 次数大于1需要修复
                        iniPop[re][j] = 0;
                }
                // 未出现数字的数组
                vector<int> intList;
                for (int j = 0; j < length; j++)
                    if (njs[j] == 0)
                        // 将未出现的数添加至数组中
                        intList.push_back(j + 1);
                // 乱序
                random_shuffle(intList.begin(), intList.end());
                int k = 0;
                for (int j = 0; j < length; j++)
                    if (iniPop[re][j] == 0)
                        // 填入
                        iniPop[re][j] = intList[k++];
            }
        }
    }

    // 变异
    for (int i = 0; i < popNum; i++)
        // 按变异概率，交换两个基因
        if (dist(random) <= pMutate) {
            // 位置1的基因
            int pos1 = random(rd) % length;
            // 位置2的基因
            int pos2 = random(rd) % length;
            while (pos1 == pos2)
                // 位置相同，重新获取位置
                pos2 = random(rd) % length;
            // 交换基因
            int t = iniPop[i][pos1];
            iniPop[i][pos1] = iniPop[i][pos2];
            iniPop[i][pos2] = t;
        }
}

int get_code_pos(int code, int codeNum, int* codes) {
    int pos = 0;
    for (; pos < codeNum; pos++)
        if (code == codes[pos])
            return pos;
    return -1;
}